package com.learn.algorithm_300;

import org.junit.Test;

import java.util.HashMap;
import java.util.Map;

/**
 * 最长递增子序列，打印子序列
 *
 * @author gatts, 2024/3/8 20:09
 */
public class TestDP {

    @Test
    public void test() {
        // int[] nums = {1, 5, 2, 4, 3};
        int[] nums = {10, 9, 2, 5, 3, 7, 101, 18};
        System.out.println(lengthOfLIS(nums));
    }

    public int lengthOfLIS(int[] nums) {
        int length = 1;
        for (int i = 0; i < nums.length; i++) {
            System.out.printf("main start: %d, index: %d \n", nums[i], i);
            StringBuilder baseStart = new StringBuilder(nums[i] + ",");

            length = Math.max(length, findLongestZiXu(nums, i, baseStart));

            System.out.println("main end maxLength: " + length + "\n");
        }
        System.out.println("maxLength: " + length);
        return length;
    }

    /* index -> count, 从index开始（包含）的子序列最长长度count */
    private final Map<Integer, Integer> alreadyFindMap = new HashMap<>();

    private int findLongestZiXu(int[] nums, int i, StringBuilder baseStart) {
        if (alreadyFindMap.containsKey(i)) {
            return alreadyFindMap.get(i);
        }
        int length = 1;
        for (int j = i+1; j < nums.length; j++) {
            // 存储子序列
            StringBuilder ziXu = new StringBuilder();
            ziXu.append(baseStart.toString());
            // System.out.println("nums[i],nums[j] = " + nums[i] + "," + nums[j]);
            if (nums[i] < nums[j]) {
                // System.out.println("findLongestZiXu start, index: " + j + ", num: " + nums[j]);
                ziXu.append(nums[j]).append(",");
                // j节点满足，从j继续寻找最长子序列，同时 length + 1
                length = Math.max(length, findLongestZiXu(nums, j, ziXu) + 1);
                // System.out.println("findLongestZiXu end,   index: " + j);
                String result = ziXu.substring(0, ziXu.length() - 1);
                System.out.printf("---------- find ZiXu: %s ---------- \n", result);
            }
        }
        alreadyFindMap.put(i, length);
        return length;
    }

}
